/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/divide-two-integers
   @Language: C++
   @Datetime: 19-05-31 15:55
   */

// Method 1, Time 8ms
class Solution {
	long core(long a, long b){
		if(b==1) return a;
		if(b==0) return INT_MAX;	// overflow
		if(a<0) return -core(-a,b);
		if(b<0) return -core(a,-b);
		if(a<b) return 0;
		long sum=0;
		for(long t, bit; a>=b; a-=b<<bit){
			for(t=b, bit=-1; t>0 && t<=a; t<<=1)
				++bit;
			sum+=1<<bit;
		}
		return sum;
	}
public:
	int divide(int dividend, int divisor) {
		long res = core(dividend,divisor);
		if(res>=INT_MIN && res<=INT_MAX) return res;
		else return INT_MAX;
	}
};
